import java.util.LinkedList;
import java.util.Queue;

/**
 * 101. 对称二叉树
 */
public class Solution_101 {
    /**
     * 方法二：迭代
     * <p>
     * 时间复杂度：O(N)，N 为节点数
     * <p>
     * 空间复杂度：O(N)，N 为节点数
     */
    public boolean isSymmetric(TreeNode root) {
        return checkIteration(root, root);
    }

    public boolean checkIteration(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
            p = queue.poll();
            q = queue.poll();
            if (p == null && q == null) {
                continue;
            }
            if ((p == null || q == null) || (p.val != q.val)) {
                return false;
            }
            queue.offer(p.left);
            queue.offer(q.right);
            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }

    /**
     * 方法一：递归
     * <p>
     * 通过「同步移动」两个指针的方法来遍历这棵树，
     * <p>
     * p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移；p 左移时，q 右移。
     * <p>
     * 每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
     * <p>
     * 时间复杂度：O(N)，N 为节点数
     * <p>
     * 空间复杂度：O(N)，N 为节点数
     */
    public boolean isSymmetric1(TreeNode root) {
        return checkRecursion(root, root);
    }

    public boolean checkRecursion(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && checkRecursion(p.left, q.right) && checkRecursion(p.right, q.left);
    }

    public static void main(String[] args) {
        Solution_101 solution = new Solution_101();
        TreeNode root = new TreeNode(1);
        // 测试对称树
        TreeNode left = new TreeNode(2, new TreeNode(3), new TreeNode(4));
        TreeNode right = new TreeNode(2, new TreeNode(4), new TreeNode(3));
        root.left = left;
        root.right = right;
        boolean ans = solution.isSymmetric(root);
        System.out.println(ans);
        // 测试不对称树
        left = new TreeNode(2, null, new TreeNode(3));
        right = new TreeNode(2, null, new TreeNode(3));
        root.left = left;
        root.right = right;
        ans = solution.isSymmetric(root);
        System.out.println(ans);
    }
}
